\input{euler.tex}

\begin{document}

\problem[365]{A Huge Binomial Coefficient}

The binomial coefficient $C(10^{18},10^9)$ is a number with more than 9 billion digits.

Let $M(n,k,m)$ denote the binomial coefficient $C(n,k)$ modulo $m$.

Calculate $\sum M(10^{18},10^9,p q r)$ where $1000 <p<q<r<5000$ and $p, q, r$ are prime.

\solution

To compute $M(n,k,p)$ where $p$ is prime, write $n$ and $k$ in base $p$ as
\begin{align}
n &= a_r p^r + a_{r-1} p^{r-1} + \cdots + a_0 \notag \\
k &= b_r p^r + b_{r-1} p^{r-1} + \cdots + b_0 \notag
\end{align}
and apply Lucas' theorem which states that
\begin{equation}
M(n,k,p) \equiv C(n,k) \equiv \prod_{i=0}^r C(a_i,b_i) \mod p 
\label{eq:365.1}
\end{equation}
where $C(a,b)$ is the usual binomial coefficient if $a \ge b$, and 0 if $a < b$.

For this problem, we first list all the primes between 1000 and 5000. It turns out there are 501 such primes. Then for each $p_i$, compute $r_i \equiv M(10^{18},10^9,p_i)$ using equation \eqref{eq:365.1}. Then for each combination of primes $1000 < p_1 < p_2 < p_3 < 5000$, define $x = M(10^{18},10^9,p_1 p_2 p_3)$ and solve the following congruence system
\begin{align}
x &\equiv r_i \mod p_i \notag \\
x &\equiv r_j \mod p_j \notag \\
x &\equiv r_k \mod p_k \notag
\end{align}
using the Chinese remainder theorem, which yields
\begin{equation}
x \equiv \sum_{i=1}^3 r_i \left(\prod_{j \ne i} p_j \right) \left( \prod_{j \ne i} p_j \right)_{p_i}^{-1} \mod p_1 p_2 p_3 \label{eq:365.2}
\end{equation}
where $(n)_p^{-1}$ denotes the modular multiplicative inverse of $n$ mod $p$.

Since we need to solve the congruence system for a large number of combinations of primes, we rearrange equation \eqref{eq:365.2} as
\[
x \equiv \sum_{i=1}^3 r_i \left[ \prod_{j \ne i} p_j (p_j)_{p_i}^{-1} \right] \mod p_1 p_2 p_3 . \label{eq:365.3}
\]
For each pair of primes $(p_i, p_j)$ where $r_i \ne 0$, we can pre-compute and store the value of $p_j (p_j)_{p_i}^{-1}$ (without modulo). Then we iterate all the prime triples, and solve each congruence system using the pre-computed values.

\complexity

Let $k = 10^9$ be the binomial coefficient argument. Let $n = 501$ be the number of primes in the range, and let $p = 4999$ be the largest prime.

Finding the residues of $C(k^2,k)$ modulo each prime takes $\BigO(np \log k)$ time. Building the cache for prime pairs takes $\BigO(n^2 \log p)$ time and $\BigO(n^2)$ space. We then iterate all combinations of three primes and solve the corresponding linear congruence system. There are $\BigO(n^3)$ systems to solve, and solving each takes a constant number of operations (since the number of equations is fixed at three).

Time complexity: $\BigO(np \log k + n^2 \log p + n^3)$.

Space complexity: $\BigO(n^2)$.

\answer

162619462356610313

\reference

http://en.wikipedia.org/wiki/Binomial\_coefficient

http://en.wikipedia.org/wiki/Lucas'\_theorem

http://en.wikipedia.org/wiki/Chinese\_remainder\_theorem

\end{document} 